<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>parentheses</title>
        <style>
</style>
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/katex@0.10.2/dist/katex.min.css" integrity="sha384-yFRtMMDnQtDRO8rLpMIKrtPCD5jdktao2TV19YiZYWMDkUR5GQZR/NOVTdquEx1j" crossorigin="anonymous">
<link href="https://cdn.jsdelivr.net/npm/katex-copytex@latest/dist/katex-copytex.min.css" rel="stylesheet" type="text/css">
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        <script src="https://cdn.jsdelivr.net/npm/katex-copytex@latest/dist/katex-copytex.min.js"></script>
        
    </head>
    <body class="vscode-light">
        <h1 id="parentheses">parentheses</h1>
<ul>
<li><a href="https://www.jianshu.com/p/10f5d9630818">算法思维(1)-括号问题</a></li>
</ul>
<p>本质1：括号合法匹配的本质，就是在一个字符串任意前缀里，他的左括号数量必须都大于等于右括号数量。然后最终的字符串左括号数量和右括号数量相等。</p>
<p>本质2 : 括号求表达式的本质，每一个括号内部是一个子问题，我们可以直接把子问题交给递归假设它已解决，然后只要思考如何汇总子问题的解变成全局的解的方法。</p>
<h1 id="1-leetcode-921-minimum-add-to-make-parentheses-valid">1. leetcode 921. Minimum Add to Make Parentheses Valid</h1>
<ul>
<li><a href="https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/">https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/</a></li>
</ul>
<p>针对一个只包含(和)的字符串，如果是不合法的括号情况，求加上最少的括号使得它合法。这个其实很好想，就是对每一个不合法的括号（分为两类，中间多出来的右括号，和最后没关掉的左括号）</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">minAddToMakeValid</span><span class="hljs-params">(self, S: str)</span> -&gt; int:</span>
        L = <span class="hljs-number">0</span>  <span class="hljs-comment"># 记录多余的(数目, 我们最终需要同样数目的)去平衡</span>
        R = <span class="hljs-number">0</span>  <span class="hljs-comment"># 记录多于的)数目, 我们最终需要同样数目的(去平衡</span>
        <span class="hljs-keyword">for</span> c <span class="hljs-keyword">in</span> S:
            <span class="hljs-keyword">if</span> c == <span class="hljs-string">"("</span>:
                L += <span class="hljs-number">1</span>
            <span class="hljs-keyword">else</span>:
                <span class="hljs-keyword">if</span> L &gt; <span class="hljs-number">0</span>:
                    L -= <span class="hljs-number">1</span>
                <span class="hljs-keyword">else</span>:
                    R += <span class="hljs-number">1</span>
        <span class="hljs-keyword">return</span> L+R  
</div></code></pre>
<h1 id="2-leetcode-1249-minimum-remove-to-make-valid-parentheses">2. Leetcode 1249. Minimum Remove to Make Valid Parentheses</h1>
<ul>
<li><a href="https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/">https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/</a></li>
</ul>
<h2 id="21-任意解">2.1 任意解</h2>
<p>如果只是要求数量的话，上面LC 921的代码原封不动就可以用。这里面需要求一个具体解。这个时候，就要求我们要移除正确的括号了。</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">minRemoveToMakeValid</span><span class="hljs-params">(self, s: str)</span> -&gt; str:</span>
        L = <span class="hljs-number">0</span>
        ans = []
        <span class="hljs-comment"># 第一次遍历的时候，移除多余的)</span>
        <span class="hljs-keyword">for</span> c <span class="hljs-keyword">in</span> s:
            <span class="hljs-keyword">if</span> c == <span class="hljs-string">"("</span>:
                L += <span class="hljs-number">1</span>
            <span class="hljs-keyword">elif</span> c == <span class="hljs-string">")"</span>:
                <span class="hljs-keyword">if</span> L &lt;= <span class="hljs-number">0</span>:
                    <span class="hljs-keyword">continue</span>
                L -= <span class="hljs-number">1</span>
            ans.append(c)
            
        <span class="hljs-keyword">if</span> L == <span class="hljs-number">0</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-string">""</span>.join(ans)
        
        <span class="hljs-comment"># 如果L&gt;0, 说明有多余的(, 第二次遍历，从右往左遍历删除多余的(</span>
        L2 = L
        j = len(ans) - <span class="hljs-number">1</span>
        i = len(ans) - <span class="hljs-number">1</span>
        <span class="hljs-keyword">while</span> i &gt;= <span class="hljs-number">0</span>:
            <span class="hljs-keyword">while</span> ans[i] == <span class="hljs-string">"("</span> <span class="hljs-keyword">and</span> L2:
                i -= <span class="hljs-number">1</span>
                L2 -= <span class="hljs-number">1</span>
            ans[j] = ans[i]
            j -= <span class="hljs-number">1</span>
            i -= <span class="hljs-number">1</span>
            
        <span class="hljs-keyword">return</span> <span class="hljs-string">""</span>.join(ans[L:])
</div></code></pre>
<h2 id="22-如果上面那题增加括号也要一个具体解小伙伴们想想如何改">2.2 如果上面那题增加括号也要一个具体解，小伙伴们想想如何改</h2>
<p>如果反过来，要求增加括号达到合法的括号字符串。 怎么办，其实更简单</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">minRemoveToMakeValid</span><span class="hljs-params">(self, s: str)</span> -&gt; str:</span>
        L = <span class="hljs-number">0</span>
        ans = []
        <span class="hljs-comment"># 第一次遍历的时候，移除多余的)</span>
        <span class="hljs-keyword">for</span> c <span class="hljs-keyword">in</span> s:
            <span class="hljs-keyword">if</span> c == <span class="hljs-string">"("</span>:
                L += <span class="hljs-number">1</span>
            <span class="hljs-keyword">elif</span> c == <span class="hljs-string">")"</span>:
                <span class="hljs-keyword">if</span> L &lt;= <span class="hljs-number">0</span>:
                    ans.append(<span class="hljs-string">'('</span>)
                <span class="hljs-keyword">else</span>:
                    L -= <span class="hljs-number">1</span>
            ans.append(c)
            
        <span class="hljs-keyword">if</span> L == <span class="hljs-number">0</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-string">""</span>.join(ans)
        
        <span class="hljs-comment"># 如果L&gt;0, 说明有多余的(, 在后面添加对应数目的)即可</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(L):
            ans.append(<span class="hljs-string">")"</span>)            
        <span class="hljs-keyword">return</span> <span class="hljs-string">""</span>.join(ans[L:])
</div></code></pre>
<h1 id="3-leetcode-301-最少移除括号的所有可能解">3. leetcode 301 最少移除括号的所有可能解</h1>
<ul>
<li><a href="https://leetcode.com/problems/remove-invalid-parentheses/">https://leetcode.com/problems/remove-invalid-parentheses/</a></li>
</ul>
<h2 id="31-下面的解法会超时">3.1 下面的解法会超时。</h2>
<p>先求出多余的括号数目L和R， 再利用dfs来遍历</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">removeInvalidParentheses</span><span class="hljs-params">(self, s: str)</span> -&gt; List[str]:</span>
        L = <span class="hljs-number">0</span>
        R = <span class="hljs-number">0</span>
            
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">get_L_R</span><span class="hljs-params">(t)</span>:</span>
            L2 = <span class="hljs-number">0</span>
            R2 = <span class="hljs-number">0</span>
            <span class="hljs-keyword">for</span> c <span class="hljs-keyword">in</span> t:
                <span class="hljs-keyword">if</span> c == <span class="hljs-string">"("</span>:
                    L2 += <span class="hljs-number">1</span>
                <span class="hljs-keyword">elif</span> c == <span class="hljs-string">")"</span>:
                    <span class="hljs-keyword">if</span> L2 &gt; <span class="hljs-number">0</span>:
                        L2 -= <span class="hljs-number">1</span>
                    <span class="hljs-keyword">else</span>:
                        R2 += <span class="hljs-number">1</span>
            <span class="hljs-keyword">return</span> L2, R2
        
        L, R = get_L_R(s)
                
            
        ans = set()
        t = list(s)
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_helper</span><span class="hljs-params">(t, start, end, L, R)</span>:</span>

            <span class="hljs-keyword">if</span> L == <span class="hljs-number">0</span> <span class="hljs-keyword">and</span> R == <span class="hljs-number">0</span>:
                L2, R2 = get_L_R(t) <span class="hljs-comment"># 这里必须再判断一次，t是否合法</span>
                <span class="hljs-keyword">if</span> L2+R2 == <span class="hljs-number">0</span>:
                    ans.add(<span class="hljs-string">""</span>.join(t))

            <span class="hljs-keyword">if</span> start &gt; end:  <span class="hljs-comment"># 这个判断要放到if L==0 and R==0的判断后面</span>
                <span class="hljs-keyword">return</span> 
                
            <span class="hljs-keyword">if</span> R &gt; <span class="hljs-number">0</span>:
                <span class="hljs-keyword">if</span> t[start] == <span class="hljs-string">")"</span>:
                    t[start] = <span class="hljs-string">""</span>
                    _helper(t, start+<span class="hljs-number">1</span>, end, L, R<span class="hljs-number">-1</span>)
                    t[start] = <span class="hljs-string">")"</span>
                
            <span class="hljs-keyword">if</span> L &gt; <span class="hljs-number">0</span>:
                <span class="hljs-keyword">if</span> t[end] == <span class="hljs-string">"("</span>:
                    t[end] = <span class="hljs-string">""</span>
                    _helper(t, start, end<span class="hljs-number">-1</span>, L<span class="hljs-number">-1</span>, R)
                    t[end] = <span class="hljs-string">"("</span>
            _helper(t, start+<span class="hljs-number">1</span>, end, L, R)
            _helper(t, start, end<span class="hljs-number">-1</span>, L, R)
                
        _helper(t, <span class="hljs-number">0</span>, len(s)<span class="hljs-number">-1</span>, L, R)
        <span class="hljs-keyword">return</span> list(ans)
</div></code></pre>
<h2 id="32-bfs解法">3.2 BFS解法</h2>
<p>如果字符串不合法，那么就需要删除若干个字符才合法。 下面就是用bfs方式来逐级删除字符</p>
<ol>
<li>level_0, 不删除字符，验证是否合法</li>
<li>level_1, 删除1个字符后，验证是否合法</li>
<li>level_2, 删除2个字符后，验证是否合法</li>
<li>...</li>
</ol>
<p>注意，下面的代码有一个巧妙的假设，那就是符合条件的字符串，一定都在同一个level里面</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">removeInvalidParentheses</span><span class="hljs-params">(self, s: str)</span> -&gt; List[str]:</span>
        <span class="hljs-comment"># initialize a set with one element</span>
        <span class="hljs-comment"># set is used here in order to avoid duplicate element</span>
        level = {s}
        <span class="hljs-keyword">while</span> <span class="hljs-literal">True</span>:
            valid = []
            <span class="hljs-keyword">for</span> elem <span class="hljs-keyword">in</span> level:
                <span class="hljs-keyword">if</span> self.isValid(elem):
                    valid.append(elem)
            <span class="hljs-keyword">if</span> valid:
                <span class="hljs-keyword">return</span> valid
            <span class="hljs-comment"># initialize an empty set</span>
            new_level = set()
            <span class="hljs-comment"># BFS</span>
            <span class="hljs-keyword">for</span> elem <span class="hljs-keyword">in</span> level:
                <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(len(elem)):
                    new_level.add(elem[:i] + elem[i + <span class="hljs-number">1</span>:])
            level = new_level
    
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">isValid</span><span class="hljs-params">(self,s)</span>:</span>
        count = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> c <span class="hljs-keyword">in</span> s:
            <span class="hljs-keyword">if</span> c == <span class="hljs-string">'('</span>:
                count += <span class="hljs-number">1</span>
            <span class="hljs-keyword">elif</span> c == <span class="hljs-string">')'</span>:
                count -= <span class="hljs-number">1</span>
                <span class="hljs-keyword">if</span> count &lt; <span class="hljs-number">0</span>:
                    <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
        <span class="hljs-keyword">return</span> count == <span class="hljs-number">0</span>
</div></code></pre>
<h1 id="4-leetcode-32-longest-valid-parentheses">4. LeetCode. 32. Longest Valid Parentheses</h1>
<ul>
<li><a href="https://leetcode.com/problems/longest-valid-parentheses/">https://leetcode.com/problems/longest-valid-parentheses/</a></li>
</ul>
<p>求包含括号的最长合法sub string, 这个简单，从左往右扫描一遍，再从右往左扫描一遍即可。</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">longestValidParentheses</span><span class="hljs-params">(self, s: str)</span> -&gt; int:</span>
        n = len(s)
        ans = <span class="hljs-number">0</span>
        level = <span class="hljs-number">0</span>
        start = <span class="hljs-number">-1</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n):
            <span class="hljs-keyword">if</span> s[i] == <span class="hljs-string">"("</span>:
                level += <span class="hljs-number">1</span>
            <span class="hljs-keyword">else</span>:
                level -= <span class="hljs-number">1</span>
            
            <span class="hljs-keyword">if</span> level == <span class="hljs-number">0</span>:
                ans = max(ans, i-start)
            <span class="hljs-keyword">if</span> level &lt; <span class="hljs-number">0</span>:
                start = i
                level = <span class="hljs-number">0</span>
                
        level = <span class="hljs-number">0</span>
        start = n
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n<span class="hljs-number">-1</span>, <span class="hljs-number">-1</span>, <span class="hljs-number">-1</span>):
            <span class="hljs-keyword">if</span> s[i] == <span class="hljs-string">")"</span>:
                level += <span class="hljs-number">1</span>
            <span class="hljs-keyword">else</span>:
                level -= <span class="hljs-number">1</span>
            <span class="hljs-keyword">if</span> level == <span class="hljs-number">0</span>:
                ans = max(ans, start-i)
            <span class="hljs-keyword">if</span> level &lt; <span class="hljs-number">0</span>:
                start = i
                level = <span class="hljs-number">0</span>
        <span class="hljs-keyword">return</span> ans
    
</div></code></pre>
<p>如果字符串里面只包含括号，不包含其他字符，可以用下面的简化算法</p>
<pre><code class="language-java"><div><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">longestValidParentheses</span><span class="hljs-params">(String s)</span> </span>{
        String rev = <span class="hljs-keyword">new</span> StringBuilder(s).reverse().toString();
        <span class="hljs-keyword">return</span> Math.max(help(s, <span class="hljs-string">'('</span>, <span class="hljs-string">')'</span>), help(rev, <span class="hljs-string">')'</span>, <span class="hljs-string">'('</span>));
    }
    <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">help</span><span class="hljs-params">(String s, <span class="hljs-keyword">char</span> L, <span class="hljs-keyword">char</span> R)</span> </span>{
        <span class="hljs-keyword">int</span> leftCnt = <span class="hljs-number">0</span>, rightCnt = <span class="hljs-number">0</span>, res = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">char</span> c : s.toCharArray()) {
            <span class="hljs-keyword">if</span> (c == L) leftCnt++;
            <span class="hljs-keyword">else</span> rightCnt++;
            <span class="hljs-keyword">if</span> (leftCnt == rightCnt) res = Math.max(res, <span class="hljs-number">2</span> * leftCnt);
            <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (rightCnt &gt; leftCnt) {
                rightCnt = leftCnt = <span class="hljs-number">0</span>;
            }
        }
        <span class="hljs-keyword">return</span> res;
    }
</div></code></pre>
<p>这道题的dp解法很难记，还是放弃了。</p>
<h1 id="5-lc-678-valid-parenthesis-string">5. LC 678. Valid Parenthesis String</h1>
<ul>
<li><a href="https://leetcode.com/problems/valid-parenthesis-string/">https://leetcode.com/problems/valid-parenthesis-string/</a></li>
</ul>
<p>带通配符的括号是否匹配, 其实就是说*既可以被当做左括号或者右括号或者空白字符。看这个字符串是否匹配。
其实本质就是在维护括号匹配的2大特性。如果当中出现了右括号不合法，我们就看之前的通配符用作左括号。如果最后是左括号多出来了，我们就维护一个变量，尽可能压缩之前的左括号。
所以我们就有了一个容错区间，LMIN是防止左括号用不完的情况所以代表，只要左括号多出来了，我来一个通配符我都当它是右括号。 LMAX代表，希望左括号越多越好，这样万一后面来了很多右括号，我也有很多储备尽可能不被击穿。</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">checkValidString</span><span class="hljs-params">(self, s: str)</span> -&gt; bool:</span>
        Lmin = <span class="hljs-number">0</span>
        Lmax = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> c <span class="hljs-keyword">in</span> s:
            <span class="hljs-keyword">if</span> c == <span class="hljs-string">"("</span>:
                Lmin += <span class="hljs-number">1</span>
                Lmax += <span class="hljs-number">1</span>
            <span class="hljs-keyword">elif</span> c == <span class="hljs-string">"*"</span>: <span class="hljs-comment"># 通配符，提升左括号上限，同时降低左括号下限，防止左括号过多</span>
                Lmax += <span class="hljs-number">1</span>
                Lmin -= <span class="hljs-number">1</span>
            <span class="hljs-keyword">else</span>:
                Lmax -= <span class="hljs-number">1</span>
                Lmin -= <span class="hljs-number">1</span>
            <span class="hljs-keyword">if</span> Lmax &lt; <span class="hljs-number">0</span>:  <span class="hljs-comment"># 左括号上限被右括号击穿了，就彻底不合法</span>
                <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
            Lmin = max(Lmin, <span class="hljs-number">0</span>)
            
        <span class="hljs-keyword">return</span> Lmin == <span class="hljs-number">0</span>
</div></code></pre>
<p>这道题的dp解法也很难记，还是放弃了。</p>
<h1 id="6-lc-856-score-of-parentheses">6. LC. 856. Score of Parentheses</h1>
<ul>
<li><a href="https://leetcode.com/problems/score-of-parentheses/">https://leetcode.com/problems/score-of-parentheses/</a></li>
</ul>
<p>Given a balanced parentheses string S, compute the score of the string based on the following rule:</p>
<ul>
<li>() has score 1</li>
<li>AB has score A + B, where A and B are balanced parentheses strings.</li>
<li>(A) has score 2 * A, where A is a balanced parentheses string.</li>
</ul>
<pre><code><code><div>Example 1:

Input: &quot;()&quot;
Output: 1
Example 2:

Input: &quot;(())&quot;
Output: 2
Example 3:

Input: &quot;()()&quot;
Output: 2
Example 4:

Input: &quot;(()(()))&quot;
Output: 6
</div></code></code></pre>
<p>我参考四则运算计算器的思路的解法</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">scoreOfParentheses</span><span class="hljs-params">(self, S: str)</span> -&gt; int:</span>
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_helper</span><span class="hljs-params">(tokens)</span>:</span>
  
            stack = []
            <span class="hljs-keyword">while</span> tokens:
                token = tokens.pop(<span class="hljs-number">0</span>)
                <span class="hljs-keyword">if</span> token == <span class="hljs-string">"("</span>:
                    r = _helper(tokens)
                    <span class="hljs-keyword">if</span> r == <span class="hljs-number">0</span>:
                        stack.append(<span class="hljs-number">1</span>)
                    <span class="hljs-keyword">else</span>:
                        stack.append(r * <span class="hljs-number">2</span>)
                <span class="hljs-keyword">else</span>:
                    <span class="hljs-keyword">return</span> sum(stack)
            
            <span class="hljs-keyword">return</span> sum(stack) 
        <span class="hljs-keyword">return</span> _helper(list(S))

</div></code></pre>
<p>转换成二叉树的思路</p>
<p>这道题，其实() 就是叶子节点，他的分数为1分。
内部节点其实就是外层的括号，他的函数就是对他的孩子节点返回的值求和 然后再乘以2.
所以一个这样的表达式可以画成如下的树((()())())</p>
<p><img src="file:///e:\gitee\leetcode\stack\pics\parentheses.png" alt="parentheses.png"></p>
<p>这里整个表达式 是个根节点。</p>
<pre><code class="language-java"><div><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">scoreOfParentheses</span><span class="hljs-params">(String S)</span> </span>{
    <span class="hljs-keyword">int</span> depth = <span class="hljs-number">0</span>, res = <span class="hljs-number">0</span>;
    <span class="hljs-keyword">char</span>[] cs = S.toCharArray();
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; cs.length; i++) {
        <span class="hljs-keyword">if</span> (cs[i] == <span class="hljs-string">'('</span>) depth++;
        <span class="hljs-keyword">else</span> {
            depth--;
            <span class="hljs-keyword">if</span> (cs[i - <span class="hljs-number">1</span>] == <span class="hljs-string">'('</span>) 
                res += <span class="hljs-number">1</span> &lt;&lt; depth; <span class="hljs-comment">// 叶子节点，把父亲们积累的DEPTH一次作用上</span>
        }
    }
    <span class="hljs-keyword">return</span> res;
}
</div></code></pre>
<h1 id="7-lc-394-decode-string">7. LC. 394. Decode String</h1>
<ul>
<li><a href="https://leetcode.com/problems/decode-string/">https://leetcode.com/problems/decode-string/</a></li>
</ul>
<pre><code><code><div>Example 1:

Input: s = &quot;3[a]2[bc]&quot;
Output: &quot;aaabcbc&quot;

Example 2:

Input: s = &quot;3[a2[c]]&quot;
Output: &quot;accaccacc&quot;
</div></code></code></pre>
<p>我参考四则计算器的代码</p>
<pre><code class="language-python"><div><span class="hljs-keyword">import</span> re

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">decodeString</span><span class="hljs-params">(self, s: str)</span> -&gt; str:</span>
        tokens = re.findall(<span class="hljs-string">r"\d+|\[|\]|[a-zA-Z]+"</span>, s)
        print(tokens)
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_helper</span><span class="hljs-params">(tokens)</span>:</span>
            s = []
            num = <span class="hljs-number">1</span>
    
            <span class="hljs-keyword">while</span> tokens:
                token = tokens.pop(<span class="hljs-number">0</span>)
                
                <span class="hljs-keyword">if</span> token == <span class="hljs-string">"["</span>:
                    token = _helper(tokens)
                <span class="hljs-keyword">elif</span> token == <span class="hljs-string">"]"</span>:
                    <span class="hljs-keyword">return</span> <span class="hljs-string">""</span>.join(s)
                
                <span class="hljs-keyword">if</span> token.isdigit():
                    num = int(token)
                <span class="hljs-keyword">else</span>:
                    s.append(num*token)
                    num = <span class="hljs-number">1</span>   <span class="hljs-comment"># 这里重置num = 1 很关键</span>
                
            <span class="hljs-keyword">return</span> <span class="hljs-string">""</span>.join(s)
                
        <span class="hljs-keyword">return</span> _helper(tokens)
</div></code></pre>
<h1 id="8-lc-1190-reverse-substrings-between-each-pair-of-parentheses">8. LC 1190. Reverse Substrings Between Each Pair of Parentheses</h1>
<ul>
<li><a href="https://leetcode.com/problems/reverse-substrings-between-each-pair-of-parentheses/">https://leetcode.com/problems/reverse-substrings-between-each-pair-of-parentheses/</a></li>
</ul>
<p>翻转括号里面的字符串</p>
<pre><code><code><div>Example 1:
Input: s = &quot;(abcd)&quot;
Output: &quot;dcba&quot;

Example 2:
Input: s = &quot;(u(love)i)&quot;
Output: &quot;iloveu&quot;
Explanation: The substring &quot;love&quot; is reversed first, then the whole string is reversed.

Example 3:
Input: s = &quot;(ed(et(oc))el)&quot;
Output: &quot;leetcode&quot;
Explanation: First, we reverse the substring &quot;oc&quot;, then &quot;etco&quot;, and finally, the whole string.

Example 4:
Input: s = &quot;a(bcdefghijkl(mno)p)q&quot;
Output: &quot;apmnolkjihgfedcbq&quot;
</div></code></code></pre>
<p>我参考四则计算器的代码</p>
<pre><code class="language-python"><div><span class="hljs-keyword">import</span> re

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">reverseParentheses</span><span class="hljs-params">(self, s: str)</span> -&gt; str:</span>
        tokens = re.findall(<span class="hljs-string">r"\(|\)|\w+"</span>, s)
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_helper</span><span class="hljs-params">(tokens)</span>:</span>
            st = []
            <span class="hljs-keyword">while</span> tokens:
                token = tokens.pop(<span class="hljs-number">0</span>)
                <span class="hljs-keyword">if</span> token == <span class="hljs-string">"("</span>:
                    token = _helper(tokens)
                <span class="hljs-keyword">elif</span> token == <span class="hljs-string">")"</span>:    
                    t = <span class="hljs-string">""</span>.join(st)
                    <span class="hljs-keyword">return</span> t[::<span class="hljs-number">-1</span>]
                
                
                st.append(token)
                
            <span class="hljs-keyword">return</span> <span class="hljs-string">""</span>.join(st)
            
        <span class="hljs-keyword">return</span> _helper(tokens)
    
</div></code></pre>
<h1 id="9-lc-number-of-atoms">9. LC Number of Atoms</h1>
<ul>
<li><a href="https://leetcode.com/problems/number-of-atoms/">https://leetcode.com/problems/number-of-atoms/</a></li>
</ul>
<p>将 &quot;K4(ON(SO3)2)2&quot; 转换为 &quot;K4N2O14S4&quot;</p>
<p>``
Example 1:
Input:
formula = &quot;H2O&quot;
Output: &quot;H2O&quot;
Explanation:
The count of elements are {'H': 2, 'O': 1}.</p>
<p>Example 2:
Input:
formula = &quot;Mg(OH)2&quot;
Output: &quot;H2MgO2&quot;
Explanation:
The count of elements are {'H': 2, 'Mg': 1, 'O': 2}.</p>
<p>Example 3:
Input:
formula = &quot;K4(ON(SO3)2)2&quot;
Output: &quot;K4N2O14S4&quot;
Explanation:
The count of elements are {'K': 4, 'N': 2, 'O': 14, 'S': 4}.</p>
<pre><code><code><div>

&quot;K4(ON(SO3)2)2&quot; = K*4 + (O + N + (S + O*3) * 2) * 2 = &quot;K4N2O14S4&quot;


我参考四则计算器的代码

```python
import re

def atom_multi(d, num):
    keys = d.keys()
    for k in keys:
        d[k] = d[k] * num
    return d
        
def atom_sum(d_list):
    d0 = {}
    for d in d_list:
        for k,v in d.items():
            if k in d0:
                d0[k] += d[k]
            else:
                d0[k] = d[k]
    return d0

class Solution:
    def countOfAtoms(self, formula: str) -&gt; str:
        tokens = re.findall(r&quot;\(|\)|\d+|[A-Z][a-z]*&quot;, formula)
        #print(tokens)
        
        def _helper(tokens):
            st = []
            num = 1
            atom = &quot;&quot;
            while tokens:
                token = tokens.pop(0)
                if token == &quot;(&quot;:
                    token = _helper(tokens)
                elif token == &quot;)&quot;:
                    return atom_sum(st)

                if type(token) is dict:
                    st.append(token)
                elif token.isdigit():
                    num = int(token)
                    atom = st.pop()
                    st.append(atom_multi(atom, num))
                else:
                    atom = {token:1}
                    st.append(atom)

            return atom_sum(st)
        
        d = _helper(tokens)
        keys = list(d.keys())
        keys.sort()
        ans = []
        for k in keys:
            if d[k] &gt; 1:
                ans.append(&quot;{}{}&quot;.format(k,d[k]))
            else:
                ans.append(k)
        return &quot;&quot;.join(ans)
  
        
</div></code></code></pre>
<p>有人用同样的思路，写的比我简洁 <a href="https://leetcode.com/problems/number-of-atoms/discuss/109333/Neat-Python-with-Explanation-35ms">https://leetcode.com/problems/number-of-atoms/discuss/109333/Neat-Python-with-Explanation-35ms</a></p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span><span class="hljs-params">(object)</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">countOfAtoms</span><span class="hljs-params">(self, formula)</span>:</span>
        <span class="hljs-keyword">import</span> re
        <span class="hljs-keyword">from</span> collections <span class="hljs-keyword">import</span> defaultdict
        tokens = list(filter(<span class="hljs-keyword">lambda</span> c: c, re.split(<span class="hljs-string">'([A-Z]{1}[a-z]?|\(|\)|\d+)'</span>, formula)))
        stack, i = [defaultdict(int)], <span class="hljs-number">0</span>
        <span class="hljs-keyword">while</span> i &lt; len(tokens):
            token = tokens[i]
            <span class="hljs-keyword">if</span> token == <span class="hljs-string">'('</span>:
                stack.append(defaultdict(int))
            <span class="hljs-keyword">else</span>:
                count = <span class="hljs-number">1</span>
                <span class="hljs-comment"># Check if next token is a number.</span>
                <span class="hljs-keyword">if</span> i + <span class="hljs-number">1</span> &lt; len(tokens) <span class="hljs-keyword">and</span> re.search(<span class="hljs-string">'^\d+$'</span>, tokens[i + <span class="hljs-number">1</span>]):
                    count, i = int(tokens[i + <span class="hljs-number">1</span>]), i + <span class="hljs-number">1</span>
                atoms = stack.pop() <span class="hljs-keyword">if</span> token == <span class="hljs-string">')'</span> <span class="hljs-keyword">else</span> { token: <span class="hljs-number">1</span> }
                <span class="hljs-comment"># Combine counts of atoms.</span>
                <span class="hljs-keyword">for</span> atom <span class="hljs-keyword">in</span> atoms:
                    stack[<span class="hljs-number">-1</span>][atom] += atoms[atom] * count
            i += <span class="hljs-number">1</span>
        <span class="hljs-keyword">return</span> <span class="hljs-string">''</span>.join([atom + (str(count) <span class="hljs-keyword">if</span> count &gt; <span class="hljs-number">1</span> <span class="hljs-keyword">else</span> <span class="hljs-string">''</span>) <span class="hljs-keyword">for</span> atom, count <span class="hljs-keyword">in</span> sorted(stack[<span class="hljs-number">-1</span>].items())])
</div></code></pre>
<h1 id="10-lc-736-parse-lisp-expression">10. LC 736. Parse Lisp Expression</h1>
<ul>
<li><a href="https://leetcode.com/problems/parse-lisp-expression/">https://leetcode.com/problems/parse-lisp-expression/</a></li>
</ul>
<p>解析 Lisp-like expression,  只支持 let, add, multi 三种操作符号</p>
<pre><code><code><div>Input: (add 1 2)
Output: 3

Input: (mult 3 (add 2 3))
Output: 15

Input: (let x 2 (mult x 5))
Output: 10

Input: (let x 2 (mult x (let x 3 y 4 (add x y))))
Output: 14
Explanation: In the expression (add x y), when checking for the value of the variable x,
we check from the innermost scope to the outermost in the context of the variable we are trying to evaluate.
Since x = 3 is found first, the value of x is 3.

Input: (let x 3 x 2 x)
Output: 2
Explanation: Assignment in let statements is processed sequentially.

Input: (let x 1 y 2 x (add x y) (add x y))
Output: 5
Explanation: The first (add x y) evaluates as 3, and is assigned to x.
The second (add x y) evaluates as 3+2 = 5.

Input: (let x 2 (add (let x 3 (let x 4 x)) x))
Output: 6
Explanation: Even though (let x 4 x) has a deeper scope, it is outside the context
of the final x in the add-expression.  That final x will equal 2.

Input: (let a1 3 b2 (add a1 1) b2) 
Output 4
Explanation: Variable names can contain digits after the first character.
</div></code></code></pre>
<p>我参考四则计算器的代码</p>
<pre><code class="language-python"><div><span class="hljs-keyword">import</span> re

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">evaluate</span><span class="hljs-params">(self, expression: str)</span> -&gt; int:</span>
        tokens = re.findall(<span class="hljs-string">r"\(|\)|let|add|mult|\-?\d+|[a-z]+[0-9]*"</span>, expression)
        <span class="hljs-comment">#print(tokens)</span>
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_helper</span><span class="hljs-params">(tokens, scope_father)</span>:</span>
            scope = {}
            scope.update(scope_father)
            op = <span class="hljs-string">""</span>
            stack = []
            <span class="hljs-keyword">while</span> tokens:
                token = tokens.pop(<span class="hljs-number">0</span>)
                <span class="hljs-comment">#print(token)</span>
                <span class="hljs-keyword">if</span> token == <span class="hljs-string">"("</span>:
                    token = _helper(tokens, scope)
                <span class="hljs-keyword">elif</span> token == <span class="hljs-string">")"</span>:
                    result = stack.pop(<span class="hljs-number">0</span>)
                    <span class="hljs-keyword">if</span> type(result) <span class="hljs-keyword">is</span> int:
                        <span class="hljs-keyword">return</span> result
                    <span class="hljs-keyword">else</span>:
                        <span class="hljs-keyword">return</span> scope[result]

                <span class="hljs-keyword">if</span> token <span class="hljs-keyword">in</span> [<span class="hljs-string">"let"</span>, <span class="hljs-string">"add"</span>, <span class="hljs-string">"mult"</span>]:
                    op = token
                <span class="hljs-keyword">else</span>:
                    <span class="hljs-keyword">try</span>:
                        token = int(token)
                    <span class="hljs-keyword">except</span> Exception <span class="hljs-keyword">as</span> e:
                        <span class="hljs-keyword">pass</span>
                    stack.append(token)
                    
                <span class="hljs-keyword">if</span> len(stack) == <span class="hljs-number">2</span>:
                    val1 = stack.pop(<span class="hljs-number">0</span>)
                    val2 = stack.pop(<span class="hljs-number">0</span>)
                    <span class="hljs-keyword">if</span> op == <span class="hljs-string">"let"</span>:
                        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> type(val2) <span class="hljs-keyword">is</span> int:  <span class="hljs-comment"># for case "(let x -2 y x y)"</span>
                            val2 = scope[val2]
                        scope[val1] = val2
                    <span class="hljs-keyword">elif</span> op == <span class="hljs-string">"add"</span>:
                        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> type(val1) <span class="hljs-keyword">is</span> int:
                            val1 = scope[val1]
                        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> type(val2) <span class="hljs-keyword">is</span> int:
                            val2 = scope[val2]
                        stack.append(val1 + val2)
                    <span class="hljs-keyword">else</span>:
                        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> type(val1) <span class="hljs-keyword">is</span> int:
                            val1 = scope[val1]
                        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> type(val2) <span class="hljs-keyword">is</span> int:
                            val2 = scope[val2]
                        stack.append(val1 * val2)                        
                        
            result = stack.pop(<span class="hljs-number">0</span>)
            <span class="hljs-keyword">if</span> type(result) <span class="hljs-keyword">is</span> int:
                <span class="hljs-keyword">return</span> result
            <span class="hljs-keyword">else</span>:
                <span class="hljs-keyword">return</span> scope[result]
            
        <span class="hljs-keyword">return</span> _helper(tokens, {})
    
    
</div></code></pre>
<h1 id="11-四则计算器">11. 四则计算器</h1>
<pre><code class="language-python"><div>
<span class="hljs-keyword">import</span> re

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">calculator</span><span class="hljs-params">(s)</span>:</span>
    tokens = re.findall(<span class="hljs-string">"\(|\)|\+|\-|\*|\/|\d+"</span>, s)
    print(tokens)

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_helper</span><span class="hljs-params">(tokens)</span>:</span>
        stack = []
        op = <span class="hljs-string">"+"</span>

        <span class="hljs-keyword">while</span> tokens:
            token = tokens.pop(<span class="hljs-number">0</span>)
            <span class="hljs-comment"># (1)第一个if判断阶段</span>
            <span class="hljs-keyword">if</span> token == <span class="hljs-string">"("</span>:
                <span class="hljs-comment"># 注意这里一定是 token = _helper(tokens)</span>
                <span class="hljs-comment"># 不能写成 stack.append(_helper(tokens)), 如果括号前面是*， token还需要参加后面的计算</span>
                token = _helper(tokens)    
            <span class="hljs-keyword">elif</span> token == <span class="hljs-string">")"</span>:
                <span class="hljs-keyword">return</span> sum(stack)

            <span class="hljs-comment"># (2)第二个if判断阶段</span>
            <span class="hljs-keyword">if</span> token <span class="hljs-keyword">in</span> [<span class="hljs-string">"+"</span>, <span class="hljs-string">"-"</span>, <span class="hljs-string">"*"</span>, <span class="hljs-string">"/"</span>]:
                op = token
            <span class="hljs-keyword">else</span>:
                <span class="hljs-keyword">if</span> op == <span class="hljs-string">"+"</span>:
                    stack.append(int(token))
                <span class="hljs-keyword">elif</span> op == <span class="hljs-string">"-"</span>:
                    stack.append(-int(token))
                <span class="hljs-keyword">elif</span> op == <span class="hljs-string">"*"</span>:
                    p1 = stack.pop()
                    p2 = int(token)
                    stack.append(p1 * p2)
                <span class="hljs-keyword">elif</span> op == <span class="hljs-string">"/"</span>:
                    p1 = stack.pop()
                    p2 = int(token)
                    stack.append(p1 / p2)

        <span class="hljs-keyword">return</span> sum(stack)


    <span class="hljs-keyword">return</span> _helper(tokens)
</div></code></pre>
<h1 id="12-lc-brace-expansion-ii">12. LC Brace Expansion II</h1>
<ul>
<li><a href="https://leetcode.com/problems/brace-expansion-ii/">https://leetcode.com/problems/brace-expansion-ii/</a></li>
</ul>
<p>集合的计算。支持并集， 和笛卡尔乘积两种运算</p>
<pre><code><code><div>Example 1:
Input: &quot;{a,b}{c,{d,e}}&quot;
Output: [&quot;ac&quot;,&quot;ad&quot;,&quot;ae&quot;,&quot;bc&quot;,&quot;bd&quot;,&quot;be&quot;]

Example 2:
Input: &quot;{{a,z},a{b,c},{ab,z}}&quot;
Output: [&quot;a&quot;,&quot;ab&quot;,&quot;ac&quot;,&quot;z&quot;]
Explanation: Each distinct word is written only once in the final answer.
</div></code></code></pre>
<pre><code class="language-python"><div><span class="hljs-keyword">import</span> re

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">braceExpansionII</span><span class="hljs-params">(self, expression: str)</span> -&gt; List[str]:</span>

        <span class="hljs-comment"># (1) helper function</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_sum</span><span class="hljs-params">(stack)</span>:</span>
            s = set()
            <span class="hljs-keyword">for</span> ss <span class="hljs-keyword">in</span> stack:
                <span class="hljs-keyword">if</span> type(ss) <span class="hljs-keyword">is</span> str:
                    ss = {ss}
                s = s | ss
            <span class="hljs-keyword">return</span> s
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_multi</span><span class="hljs-params">(token1, token2)</span>:</span>
            <span class="hljs-keyword">if</span> type(token1) <span class="hljs-keyword">is</span> str:
                token1 = [token1]
            <span class="hljs-keyword">if</span> type(token2) <span class="hljs-keyword">is</span> str:
                token2 = [token2]
            s = set()
            <span class="hljs-keyword">for</span> a <span class="hljs-keyword">in</span> token1:
                <span class="hljs-keyword">for</span> b <span class="hljs-keyword">in</span> token2:
                    s.add(a+b)
            <span class="hljs-comment">#print(f"multi token1={token1} token2={token2} s={s}")</span>
            <span class="hljs-keyword">return</span> s
        
        <span class="hljs-comment"># (2) convert expression</span>
        <span class="hljs-comment"># "{{a,z},a{b,c},{ab,z}}" =&gt; "{{a+z}+a*{b+c}+{ab+z}}"</span>
        expression = expression.replace(<span class="hljs-string">"}{"</span>, <span class="hljs-string">"}*{"</span>)
        expression = expression.replace(<span class="hljs-string">","</span>, <span class="hljs-string">"+"</span>)
        
        tokens0 = re.findall(<span class="hljs-string">r"\{|\}|\+|\*|\w+"</span>, expression)
        tokens = []
        <span class="hljs-keyword">for</span> i,token <span class="hljs-keyword">in</span> enumerate(tokens0):
            <span class="hljs-keyword">if</span> token == <span class="hljs-string">"{"</span>:
                <span class="hljs-keyword">if</span> i &gt; <span class="hljs-number">0</span> <span class="hljs-keyword">and</span> tokens0[i<span class="hljs-number">-1</span>].isalpha():
                    tokens.append(<span class="hljs-string">"*"</span>)
                    tokens.append(token)
                <span class="hljs-keyword">else</span>:
                    tokens.append(token)
            <span class="hljs-keyword">elif</span> token == <span class="hljs-string">"}"</span>:
                <span class="hljs-keyword">if</span> i &lt; len(tokens0) - <span class="hljs-number">1</span> <span class="hljs-keyword">and</span> tokens0[i+<span class="hljs-number">1</span>].isalpha():
                    tokens.append(token)
                    tokens.append(<span class="hljs-string">"*"</span>)
                <span class="hljs-keyword">else</span>:
                    tokens.append(token)
            <span class="hljs-keyword">else</span>:
                tokens.append(token)
            
        <span class="hljs-comment">#print(expression)</span>
        <span class="hljs-comment">#print(tokens)</span>
            
        <span class="hljs-comment"># (3) caculator</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_helper</span><span class="hljs-params">(tokens)</span>:</span>
            stack = []
            op = <span class="hljs-string">"+"</span>
            <span class="hljs-keyword">while</span> tokens:
                token = tokens.pop(<span class="hljs-number">0</span>)
                <span class="hljs-comment">#print(f"{token} {stack}")</span>
                <span class="hljs-keyword">if</span> token == <span class="hljs-string">"{"</span>:
                    token = _helper(tokens)
                <span class="hljs-keyword">elif</span> token == <span class="hljs-string">"}"</span>:
                    <span class="hljs-keyword">return</span> _sum(stack)
                
                <span class="hljs-keyword">if</span> token <span class="hljs-keyword">in</span> [<span class="hljs-string">"+"</span>, <span class="hljs-string">"*"</span>]:
                    op = token
                <span class="hljs-keyword">else</span>:
                    <span class="hljs-keyword">if</span> op == <span class="hljs-string">"+"</span>:
                        stack.append(token)
                    <span class="hljs-keyword">else</span>:
                        last_token = stack.pop()
                        new_token = _multi(last_token, token)
                        stack.append(new_token)
            <span class="hljs-comment">#print(f"final {stack}")</span>
            <span class="hljs-keyword">return</span> _sum(stack)
        
        <span class="hljs-keyword">return</span> sorted(list(_helper(tokens)))
 


</div></code></pre>
<h1 id="13-lc-241-different-ways-to-add-parentheses">13. LC 241. Different Ways to Add Parentheses</h1>
<ul>
<li><a href="https://leetcode.com/problems/different-ways-to-add-parentheses/">https://leetcode.com/problems/different-ways-to-add-parentheses/</a></li>
</ul>
<p>Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.</p>
<pre><code><code><div>Example 1:

Input: &quot;2-1-1&quot;
Output: [0, 2]
Explanation: 
((2-1)-1) = 0 
(2-(1-1)) = 2


Example 2:

Input: &quot;2*3-4*5&quot;
Output: [-34, -14, -10, -10, 10]
Explanation: 
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10
</div></code></code></pre>
<h2 id="解法一-错误">解法一， 错误</h2>
<p>最开始当作全排列来计算。结果里面有重复的。 主要是上面的example 2里面，按照全排列处理的话，下面的case会被算2次。但是按照本题题意，只能算做一次。</p>
<pre><code>((2*3)-(4*5)) = -14 
</code></pre>
<p>具体代码</p>
<pre><code class="language-python"><div><span class="hljs-keyword">import</span> re

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">diffWaysToCompute</span><span class="hljs-params">(self, input: str)</span> -&gt; List[int]:</span>
        tokens = re.findall(<span class="hljs-string">r"\-|\+|\*|\/|\d+"</span>, input)
        <span class="hljs-comment">#print(tokens)</span>
        nums = list(map(<span class="hljs-keyword">lambda</span> x:int(x), tokens[<span class="hljs-number">0</span>::<span class="hljs-number">2</span>]))
        ops = tokens[<span class="hljs-number">1</span>::<span class="hljs-number">2</span>]
        ans = []
        <span class="hljs-comment"># v1, dp</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_helper</span><span class="hljs-params">(nums, ops)</span>:</span>
            <span class="hljs-comment">#print(f"{nums}, {ops}")</span>
            <span class="hljs-keyword">if</span> len(nums) == <span class="hljs-number">1</span>:
                ans.append(nums[<span class="hljs-number">0</span>])
                <span class="hljs-keyword">return</span>
            n = len(ops)
            <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n):
                val1 = nums[i]
                val2 = nums[i+<span class="hljs-number">1</span>]
                <span class="hljs-keyword">if</span> ops[i] == <span class="hljs-string">"+"</span>:
                    v = val1 + val2
                <span class="hljs-keyword">elif</span> ops[i] == <span class="hljs-string">"-"</span>:
                    v = val1 - val2
                <span class="hljs-keyword">elif</span> ops[i] == <span class="hljs-string">"*"</span>:
                    v = val1 * val2
                _helper(nums[:i] + [v] + nums[i+<span class="hljs-number">2</span>:], ops[:i]+ ops[i+<span class="hljs-number">1</span>:])
        _helper(nums, ops)
        <span class="hljs-keyword">return</span> ans
    
</div></code></pre>
<h2 id="解法二-正确-按照分治方法处理">解法二， 正确。 按照分治方法处理</h2>
<pre><code class="language-python"><div><span class="hljs-keyword">import</span> re

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">diffWaysToCompute</span><span class="hljs-params">(self, input: str)</span> -&gt; List[int]:</span>
        tokens = re.findall(<span class="hljs-string">r"\-|\+|\*|\/|\d+"</span>, input)
        <span class="hljs-comment">#print(tokens)</span>
        nums = list(map(<span class="hljs-keyword">lambda</span> x:int(x), tokens[<span class="hljs-number">0</span>::<span class="hljs-number">2</span>]))
        ops = tokens[<span class="hljs-number">1</span>::<span class="hljs-number">2</span>]
        ans = []
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_helper2</span><span class="hljs-params">(nums, ops)</span>:</span>
            <span class="hljs-keyword">if</span> len(nums) == <span class="hljs-number">1</span>:
                <span class="hljs-comment">#ans.append(nums[0])</span>
                <span class="hljs-keyword">return</span> nums
            n = len(ops)
            res = []
            <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n):
                op = ops[i]
                va1 = _helper2(nums[:i+<span class="hljs-number">1</span>], ops[:i])
                va2 = _helper2(nums[i+<span class="hljs-number">1</span>:], ops[i+<span class="hljs-number">1</span>:])
                <span class="hljs-keyword">for</span> v1 <span class="hljs-keyword">in</span> va1:
                    <span class="hljs-keyword">for</span> v2 <span class="hljs-keyword">in</span> va2:
                        <span class="hljs-keyword">if</span> op == <span class="hljs-string">"+"</span>:
                            res.append(v1 + v2)
                        <span class="hljs-keyword">elif</span> op == <span class="hljs-string">"-"</span>:
                            res.append(v1 - v2)
                        <span class="hljs-keyword">else</span>:
                            res.append(v1 * v2)
            <span class="hljs-keyword">return</span> res
                
        ans = _helper2(nums, ops)
        <span class="hljs-keyword">return</span> ans
           
</div></code></pre>
<h1 id="14-lc-1541-minimum-insertions-to-balance-a-parentheses-string">14. LC 1541. Minimum Insertions to Balance a Parentheses String</h1>
<ul>
<li><a href="https://leetcode.com/problems/minimum-insertions-to-balance-a-parentheses-string/">https://leetcode.com/problems/minimum-insertions-to-balance-a-parentheses-string/</a></li>
</ul>
<p>Given a parentheses string s containing only the characters '(' and ')'. A parentheses string is balanced if:</p>
<p>Any left parenthesis '(' must have a corresponding two consecutive right parenthesis '))'.
Left parenthesis '(' must go before the corresponding two consecutive right parenthesis '))'.
In other words, we treat '(' as openning parenthesis and '))' as closing parenthesis.</p>
<p>For example, &quot;())&quot;, &quot;())(())))&quot; and &quot;(())())))&quot; are balanced, &quot;)()&quot;, &quot;()))&quot; and &quot;(()))&quot; are not balanced.</p>
<p>You can insert the characters '(' and ')' at any position of the string to balance it if needed.</p>
<p>Return the minimum number of insertions needed to make s balanced.</p>
<pre><code><code><div>Example 1:

Input: s = &quot;(()))&quot;
Output: 1
Explanation: The second '(' has two matching '))', but the first '(' has only ')' matching. We need to to add one more ')' at the end of the string to be &quot;(())))&quot; which is balanced.

Example 2:

Input: s = &quot;())&quot;
Output: 0
Explanation: The string is already balanced.

Example 3:

Input: s = &quot;))())(&quot;
Output: 3
Explanation: Add '(' to match the first '))', Add '))' to match the last '('.
</div></code></code></pre>
<p>本题要求  一个左括号匹配两个连续的右括号, 按照labuladong的微信号文章</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">minInsertions</span><span class="hljs-params">(self, s: str)</span> -&gt; int:</span>
        left_need = <span class="hljs-number">0</span>
        right_need = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> c <span class="hljs-keyword">in</span> s:
            <span class="hljs-keyword">if</span> c == <span class="hljs-string">"("</span>:
                right_need += <span class="hljs-number">2</span>
                <span class="hljs-keyword">if</span> right_need % <span class="hljs-number">2</span> == <span class="hljs-number">1</span>:
                    left_need += <span class="hljs-number">1</span>
                    right_need -= <span class="hljs-number">1</span>
            <span class="hljs-keyword">else</span>:
                right_need -= <span class="hljs-number">1</span>
                <span class="hljs-keyword">if</span> right_need &lt; <span class="hljs-number">0</span>:
                    left_need += <span class="hljs-number">1</span>
                    right_need += <span class="hljs-number">2</span>
                    
        <span class="hljs-keyword">return</span> left_need + right_need
    
</div></code></pre>
<p>如果题目的要求是, 一个左括号匹配两个右括号(右括号可以不连续). 那么把上面的代码删除3行即可</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">minInsertions</span><span class="hljs-params">(self, s: str)</span> -&gt; int:</span>
        left_need = <span class="hljs-number">0</span>
        right_need = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> c <span class="hljs-keyword">in</span> s:
            <span class="hljs-keyword">if</span> c == <span class="hljs-string">"("</span>:
                right_need += <span class="hljs-number">2</span>
            <span class="hljs-keyword">else</span>:
                right_need -= <span class="hljs-number">1</span>
                <span class="hljs-keyword">if</span> right_need &lt; <span class="hljs-number">0</span>:
                    left_need += <span class="hljs-number">1</span>
                    right_need += <span class="hljs-number">2</span>
                    
        <span class="hljs-keyword">return</span> left_need + right_need
</div></code></pre>

    </body>
    </html>